package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;

import java.util.*;

/**
 * 摆脱原始的directions走法, 改为线性的走, 整个回溯是一个高度81的搜索树.
 * <p>
 * Runtime: 19 ms, faster than 20.82% of Java online submissions for Sudoku Solver.
 *
 * @author tzp
 * @since 2020/10/26
 */
public class LC37_1 implements Backtracking {
    char[] dict = new char[9];
    char empty = '.';

    List<Set<Integer>> row = new ArrayList<>(9);
    List<Set<Integer>> col = new ArrayList<>(9);
    List<Set<Integer>> grid = new ArrayList<>(9);
    boolean hasResult = false;
    boolean[][] path = new boolean[9][9];
    char[][] board;

    public void solveSudoku(char[][] board) {
        this.board = board;
        for (int i = 0; i < 9; i++) {
            dict[i] = (char) ('1' + i);
            row.add(new HashSet<>());
            col.add(new HashSet<>());
            grid.add(new HashSet<>());
        }
        int x = -1, y = -1, v = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != empty) {
                    set(i, j, board[i][j]);
                    v++;
                } else {
                    if (x == -1) {
                        x = i;
                        y = j;
                    }
                }
            }
        }
        backtracing(x, y, v);
    }

    public void backtracing(int x, int y, int validNum) {
        for (int i = 0; i < dict.length; i++) {//先为当前格子选择数字
            char choice = dict[i];
            if (validSudoku(x, y, choice)) {
                if (validNum == 80) {
                    hasResult = true;
                    return;
                }
                set(x, y, choice);
                int index = x * 9 + y;
                for (int j = index + 1; j < 81; j++) {
                    int newX = j / 9;
                    int newY = j % 9;
                    if (!path[newX][newY]) {
                        backtracing(newX, newY, validNum + 1);
                        if (hasResult) {
                            return;
                        }
                        break;
                    }
                }
                unset(x, y, choice);
            }
        }
    }

    public boolean validSudoku(int x, int y, char c) {
        int gridIndex = (x / 3) * 3 + (y / 3);
        return !(row.get(x).contains((int) c)
                || col.get(y).contains((int) c)
                || grid.get(gridIndex).contains((int) c));
    }

    public void set(int x, int y, char c) {
        path[x][y] = true;
        board[x][y] = c;
        row.get(x).add((int) c);
        col.get(y).add((int) c);
        int gridIndex = (x / 3) * 3 + (y / 3);
        grid.get(gridIndex).add((int) c);
    }

    public void unset(int x, int y, char c) {
        path[x][y] = false;
        board[x][y] = empty;
        row.get(x).remove((int) c);
        col.get(y).remove((int) c);
        int gridIndex = (x / 3) * 3 + (y / 3);
        grid.get(gridIndex).remove((int) c);
    }

    public static void main(String[] args) {
        char[][] b = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        new LC37_1().solveSudoku(b);
        System.out.println(Arrays.deepToString(b));
    }
}
